
#include <iostream>
#include <stdexcept>
using namespace std;


// Linked list
template<typename T> class list{
public:
	// Default construction
	list() : m_head(NULL), m_tail(NULL) {}
	// Copy construction
	list( list const& that ) : m_head(NULL), m_tail(NULL){
		for(node* pnode = that.m_head; pnode; pnode = pnode->m_next)
			push_back(pnode->m_data);
	}
	// Destructor
	~list(){
		clear();
	}
	// Linked list is full ?
	bool empty(){
		return m_head == NULL && m_tail == NULL;
	}
	// Insert  front node
	void push_front(T const& data){
		m_head = new node(NULL, data, m_head);
		if(m_head->m_next)
			m_head->m_next->m_prev = m_head;
		else
			m_tail = m_head;
	}
	// Delete front node
	void pop_front(){
		if(empty())
			return;
		node* pnode = m_head->m_next;
		delete m_head;
		m_head = pnode;
		if(m_head)
			m_head->m_prev = NULL;
		else
			m_tail = NULL;
	}
	// Insert rear node
	void push_back(T const& data){
		m_tail = new node(m_tail, data, NULL);
		if(m_tail->m_prev)
			m_tail->m_prev->m_next = m_tail;
		else
			m_head = m_tail;
	}
	// Delete rear node
	void pop_back(){
		if(empty())
			return;
		node* pnode = m_tail->m_prev;
		delete m_tail;
		m_tail = pnode;
		if(m_tail)
			m_tail->m_next = NULL;
		else
			m_head = NULL;
	}
	// Get front data
	T& front(){
		if(empty())
			throw underflow_error("front(): NULL list");
		return m_head->m_data;
	}
	T const& front()const{
		return const_cast<list*>(this)->front();
	}
	// Get rear data
	T& back(){
		if(empty())
			throw overflow_error("back(): NULL list");
		return m_tail->m_data;
	}
	T const& back()const{
		return const_cast<list*>(this)->back();
	}
	// Clear the link list
	void clear(){
		while(!empty())
			pop_front();
	}
	// Get link list size
	size_t size(){
		size_t i = 0;
		for(node* pnode = m_head; pnode; pnode = pnode->m_next)
			++i;
		return i;
	}

private:
	class node{
	public:
		node(node* prev, T data, node* next) : m_prev(prev), m_data(data), m_next(next){}

		node* m_prev;	// Front pointer
		T m_data;	// Data
		node* m_next;	// Rear pointer
	};
public:
	// Forward direction iterator
	class iterator{
	public:
		iterator(node* start, node* cur, node* end)
			: m_start(start), m_cur(cur), m_end(end){}
		T& operator*(){
			if(m_cur == NULL)
				throw underflow_error("operator* : NULL node");
			return m_cur->m_data;
		}
		iterator& operator++(){
			if(m_cur == NULL)
				m_cur = m_start;
			else
				m_cur = m_cur->m_next;
			return *this;
		}
		iterator& operator--(){
			if(m_cur == NULL)
				m_cur = m_end;
			else
				m_cur = m_cur->m_prev;
			return *this;
		}
		bool operator==(iterator const& that)const{
			return m_start == that.m_start && m_cur == that.m_cur && m_end == that.m_end;
		}
		bool operator!=(iterator const& that)const{
			return !(*this==that);
		}
	private:
		node* m_start;
		node* m_cur;
		node* m_end;

		friend class list;
	};
	iterator begin(){
		return iterator(m_head, m_head, m_tail);
	}
	iterator end(){
		return iterator(m_head, NULL, m_tail);
	}
	void insert(iterator const& loc, T const& data){
		if(loc == end())
			push_back(data);
		else{
			node* pnode = new node(loc.m_cur->m_prev, data, loc.m_cur);
			if(pnode->m_prev)
				pnode->m_prev->m_next = pnode;
			else
				m_head = pnode;
			pnode->m_next->m_prev = pnode;
		}
	}
	void erase(iterator const& loc){
		if(loc == end())
			return;
		node* pnode = loc.m_cur;
		if(pnode->m_prev)
			pnode->m_prev->m_next = pnode->m_next;
		else
			m_head = pnode->m_next;
		if(pnode->m_next)
			pnode->m_next->m_prev = pnode->m_prev;
		else
			m_tail = pnode->m_prev;
		delete pnode;
	}
	/*
	 * const iterator
	 */
	class const_iterator{
	public:
		const_iterator(iterator const& it) : m_it(it){}
		T const& operator*(){
			return *m_it;
		}
		const_iterator& operator++(){
			++m_it;
			return *this;
		}
		const_iterator& operator--(){
			--m_it;
			return *this;
		}
		bool operator==(const_iterator const& that)const{
			return m_it == that.m_it;
		}
		bool operator!=(const_iterator const& that)const{
			return !(*this==that);
		}
	private:
		iterator m_it;
	};
	const_iterator cbegin()const{
		return iterator(m_head, m_head, m_tail);
	}
	const_iterator cend()const{
		return iterator(m_head, NULL, m_tail);
	}


private:
	node* m_head;	// Head
	node* m_tail;	// Tail

};

template<typename IT, typename T>
IT find(IT const& begin, IT const& end, T const& data){
	for(IT it = begin; it != end; ++it)
		if(*it == data)
			return it;
	return end;
}

template<typename IT>
void sort(IT const& begin, IT const& end){
	IT p = begin;
	IT last = end;
	--last;
	for(IT i = begin, j = last; i != j;){
		while(i != p && *i < *p)
			++i;
		if(i != p){
			swap(*i, *p);
			p = i;
		}
		while(j != p && *p < *j)
			--j;
		if(j != p){
			swap(*p, *j);
			p = j;
		}
	}
	IT it = begin;
	++it;
	if(p != begin && p != it)
		sort(begin, p);

	it = p;
	++it;
	if(it != end && it != last)
		sort(it, end);
}

template<typename T>class less{
public:
	bool operator()(T const& a, T const& b){
		return a < b;
	}
};

template<typename T>class greter{
public:
	bool operator()(T const& a, T const& b){
		return a > b;
	}
};

template<typename IT, typename CMP>
void sort(IT const& begin, IT const& end, CMP cmp){
	IT p = begin;
	IT last = end;
	--last;
	for(IT i = begin, j = last; i != j;){
		while(i != p && cmp(*i, *p))
			++i;
		if(i != p){
			swap(*i, *p);
			p = i;
		}
		while(j != p && cmp(*p, *j))
			--j;
		if(j != p){
			swap(*p, *j);
			p = j;
		}
	}
	IT it = begin;
	++it;
	if(p != begin && p != it)
		sort(begin, p, cmp);

	it = p;
	++it;
	if(it != end && it != last)
		sort(it, end, cmp);
}


// ----------------------------------------------------------------------------------


void print(string const& str, list<int> l){
	cout << str << endl;
/*	
 *	typedef list<int>::iterator IT;
 *	for(IT it = l.begin(); it != l.end(); ++it)
 *		cout << *it << ' ';
 */
	for(auto const& i : l)
		cout << i << ' ';
	cout << endl << "---------------------------------------" << endl;
}

int main(){
	list<int> ls;
	for(int i = 0; i < 5; ++i )
		ls.push_front(i+10);
	for(int i = 0; i < 5; ++i )
		ls.push_back(i+100);
	print("Before : ", ls);

	ls.pop_front();
	ls.pop_back();

	print("After : ", ls);

	ls.insert(++ls.end(), 1000);
	print("Insert : ", ls);

	ls.erase(++ls.begin());
	print("Delete : ", ls);

	typedef list<int>::iterator IT;
	IT it = ++ls.begin();
	*it = 8888;
	print("Edit", ls);

	IT fit = find(ls.begin(), ls.end(), 13);
	if(fit != ls.end())
		cout << "find : " << *fit << endl;
	else
		cout << "not find " << endl;

	sort(ls.begin(), ls.end());
	print("rise", ls);

	sort(ls.begin(), ls.end(), ::greater<int>());
	print("cmp : ", ls);
	/*
	const list<int> cls(ls);
	typedef list<int>::const_iterator CIT;
	for(CIT cit = cls.cbegin(); cit != cls.cend(); ++cit){
		cout << *cit << ' ';
	}
	cout << endl << "---------------------------------------" << endl;

	CIT cit = cls.cbegin();
//	*cit = 666;	err
	*/
	
	return 0;
}
